#include<vector>
using namespace std;
// class Solution {
// public:
//     int MoreThanHalfNum_Solution(vector<int>& numbers) {
//         sort(numbers.begin(),numbers.end());
//         int a=numbers[0];
//         int count=0;
//         for(int i=0;i<numbers.size();++i)
//         {
//             while(numbers[i]==a)
//             {
//                 count++;
//                 i++;
//             }
//             if(count>=numbers.size()/2+1)
//             {
//                 return a;
//             }
//             else{
//                 count=0;
//                 a=numbers[i];
//                 count++;
//             }
//         }
//         return a;
//     }
// };
class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        sort(gifts.begin(),gifts.end());
        int count=0;
        int flag=0;
        int res=gifts[0];
        for(auto e:gifts)
        {
            if(flag==0) res=e;
            flag+=e==res?1:-1;
        }

        
        for(auto e:gifts)
        {
            if(res==e) count++;
            else if(count>n/2)
            {
                return res;
            }
        }
        return 0;

    }
};